class Solution
{
private:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2)
    {
        ListNode dummy{};
        auto ptr = &dummy;
        while (l1 && l2)
        {
            if (l1->val < l2->val)
            {
                ptr->next = l1;
                l1 = l1->next;
            }
            else
            {
                ptr->next = l2;
                l2 = l2->next;
            }
            ptr = ptr->next;
        }
        ptr->next = l1 ? l1 : l2;
        return dummy.next;
    }
    ListNode* mergeKLists(vector<ListNode*>& lists, int i, int j)
    {
        int m = j - i;
        if (m == 0)
            return nullptr;
        if (m == 1)
            return lists[i];

        auto left = mergeKLists(lists, i, i + m / 2);
        auto right = mergeKLists(lists, i + m / 2, j);
        return mergeTwoLists(left, right);
    }
public:
    ListNode* mergeKLists(vector<ListNode*>& lists)
    {
        return mergeKLists(lists, 0, lists.size());
    }
};